package first.niuke.midding;

/**
 * @ClassName NC127
 * @description:
 * @author: 荣燊
 * @create: 2021-06-20 21:14
 **/
public class NC127 {
    /**
     * 输入： "1AB2345CD","12345EF"
     * 输出： "2345"
     */
    public static void main(String[] args) {
        String s1 = "1AB2345CD";
        String s2 = "12345EF";
        System.out.println(LCS(s1, s2));
    }


    // 最长公共子串(连续)，最长公共子序列（可以是不连续的）
    public static String LCS (String str1, String str2) {
        // write code here
        if (str1.equals(str2)) {
            return str1;
        }
        char[] chars1 = str1.toCharArray();
        char[] chars2 = str2.toCharArray();
        int[][] result = new int[chars1.length+1][chars2.length+1];
        int max = 0; // 最长公共子串的长度

        for (int i=0; i<chars1.length; i++) {
            for (int j=0; j<chars2.length; j++) {
                if (chars1[i] == chars2[j]) {
                    result[i + 1][j + 1] = result[i][j] + 1;
                    max = Math.max(result[i + 1][j + 1], max);
                }
            }
        }

        // 打印二元数组
//        System.out.print(" ");
//        for (int i = 0; i < chars2.length; i++) {
//            System.out.print(" " + chars2[i]); // 打印第一行
//        }
//        System.out.println();
//        for (int i = 1; i < result.length; i++) {
//            System.out.print(chars1[i - 1] + " ");
//            for (int j = 1; j < result[i].length; j++) {
//                System.out.print(result[i][j] + " ");
//            }
//            System.out.println();
//        }
//        System.out.println();


//        StringBuffer stringBuffer = new StringBuffer();//修改不生成新对象，推荐修改字符串时使用
//        StringBuilder stringBuilder = new StringBuilder(); //线程不安全的，相对StringBuffer有速度优势
        String s = "";
        for (int i=1; i<chars1.length+1; i++) {
            for (int j=1; j< chars2.length; j++) {
                if (result[i][j] == max) {
                    // 找出第i为结束位的字符串，长度为max
                    s = str1.substring(i-max ,i);
                    break;
                }
            }
        }
        return s;
    }
}
